//2866.美丽塔II
//https://leetcode.cn/problems/beautiful-towers-ii/
class Solution {
public:
    long long maximumSumOfHeights(vector<int>& maxHeights) {
        int n = maxHeights.size();
        long long ret = 0;
        vector<long long> prefix(n), suffix(n);
        vector<int> st;

        //单调栈
        //如果当前数字比i小 则留在栈中 如果当前数字比栈顶还小 则后面的数字不能比栈顶更大 此时后面的数字最大就是栈顶
        for (int i = 0; i < n; i++) {
            while (!st.empty() && maxHeights[i] < maxHeights[st.back()]) st.pop_back();
            
            //如果栈中没有数字 此时从该位到n的最大值为 (i+1)*maxHeights[i];
            if (st.empty()) prefix[i] = (long long)(i + 1) * maxHeights[i];
            //如果栈中有数字，表示有比i位置更小的数 则当前位置的最大值为 prefix[栈顶元素下标]+(i-栈顶元素下标(即所剩元素数))*maxHeights[i]
            else prefix[i] = prefix[st.back()] + (long long)(i - st.back()) * maxHeights[i];

            st.emplace_back(i);
        }
        st.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && maxHeights[i] < maxHeights[st.back()]) st.pop_back();
                

            if (st.empty()) suffix[i] = (long long)(n - i) * maxHeights[i];
            else suffix[i] = suffix[st.back()] + (long long)(st.back() - i) * maxHeights[i];
                
            st.emplace_back(i);
            ret = max(ret, prefix[i] + suffix[i] - maxHeights[i]);
        }
        return ret;
    }
};